/*
*
现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝
每次可以移动到右侧或下侧的相邻位置
到达珠宝架子的右下角时，停止拿取
注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1:

输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝

提示：

0 < frame.length <= 200
0 < frame[0].length <= 200

  - @author ala
  - @date 2024-09-18 14:34
*/
package main

import "fmt"

func main() {
	frame := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}

	fmt.Println(jewelleryValue(frame))
}

func jewelleryValue(frame [][]int) int {
	return V1(frame)
}

/**
 *	1）dp[i][j]表示拿到前第i,j位置时总价值
 *	2）dp[i][j] = max(dp[i - 1][j] + frame[i][j], dp[i][j - 1] + frame[i][j])
 *	3）最后dp[M][N]即为答案
 */
func V1(frame [][]int) int {
	M, N := len(frame), len(frame[0])
	var dp = make([][]int, M+1)
	for i := range dp {
		dp[i] = make([]int, N+1)
	}

	for i := 1; i <= M; i++ {
		for j := 1; j <= N; j++ {
			dp[i][j] = max(dp[i-1][j]+frame[i-1][j-1], dp[i][j-1]+frame[i-1][j-1])
		}
	}
	return dp[M][N]
}
